package com.breeze.dp;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同，具体见图。
 * 参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿，每个人也只会最多挖一次矿。
 * 要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 */


/*
解题思路:动态规划
假设n个金矿，m个工人，g[]表示每个金矿量，p[]表示每个金矿需要挖矿人
1. 最优子结构： 该题目有两个最优子结构：一个是4金矿10工人时的最优选择；一个是4金矿(10-第5个金矿所需的人数)人时的最优选择
2. 状态转移方程：
    F(n,m) = max{F(n-1,m),F(n-1,m-p[n-1])+g[n-1]},  (m>=p[n-1])
    F(n,m) = F(n-1,m), (m < p[n-1])
3. 边界条件：
    F(1,m) = g[0], (m>=p[0])
    F(1,m) = 0, (m<p[0])
 */
public class GoldMine {
    /**
     * 方法1：简单递归
     * 时间复杂度：O(2^n)
     * 空间复杂度：O(n) 递归深度
     */
    int getMaxGold(int n, int m, int[] g, int[] p) {
        if (n == 1) {
            return m >= p[0] ? g[0] : 0;
        }
        int a = getMaxGold(n - 1, m, g, p);
        if (m < p[n - 1]) {
            return a;
        }
        int b = getMaxGold(n - 1, m - p[n - 1], g, p) + g[n - 1];
        return Math.max(a, b);
    }

    // 备忘录算法使用
    Map<GoldItem, Integer> map = new HashMap<>();

    static class GoldItem {
        int n;
        int m;

        public GoldItem(int n, int m) {
            this.n = n;
            this.m = m;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            GoldItem goldItem = (GoldItem) o;
            return n == goldItem.n &&
                    m == goldItem.m;
        }

        @Override
        public int hashCode() {
            return Objects.hash(n, m);
        }
    }

    /**
     * 方法2：备忘录算法
     */
    int getMaxGold1(int n, int m, int[] g, int[] p) {
        System.out.println(map.size());
        if (n == 1) {
            return m >= p[0] ? g[0] : 0;
        }
        GoldItem goldItem = new GoldItem(n, m);
        int a;
        if (map.containsKey(goldItem)) {
            a = map.get(goldItem);
        } else {
            a = getMaxGold1(n - 1, m, g, p);
            map.put(goldItem, a);
        }
        if (m < p[n - 1]) {
            return a;
        }
        GoldItem goldItem1 = new GoldItem(n, m - p[n - 1]);
        int b;
        if (map.containsKey(goldItem1)) {
            b = map.get(goldItem1);
        } else {
            b = getMaxGold1(n - 1, m - p[n - 1], g, p);
            map.put(goldItem1, b);
        }
        return Math.max(a, b + g[n - 1]);
    }

    /**
     * 方法3：动态规划
     * cell[i,j] = max(g[i] + cell[ i-1,j-p[i] ]，cell[i-1,j])
     * 时间复杂度 O(m*n)
     * 空间复杂度 O(m*n)
     * 如果m,n较大，会带来很大的空间消耗，需要对空间进行优化
     */
    int getMaxGold2(int n, int m, int[] g, int[] p) {
        // 包含0个工人，故m+1
        int[][] cell = new int[n][m + 1];
        // n 个金矿
        for (int i = 0; i < n; i++) {
            // m 个工人
            for (int j = 0; j <= m; j++) {
                if (j < p[i]) {
                    cell[i][j] = i > 0 ? cell[i - 1][j] : 0;
                } else {
                    cell[i][j] = i > 0 ? Math.max(cell[i - 1][j], cell[i - 1][j - p[i]] + g[i]) : g[i];
                }
                System.out.printf("%3s, ", cell[i][j]);
            }
            System.out.println();
        }
        return cell[n - 1][m];
    }

    /**
     * 方法4：动态规划(优化版)
     * cell[i,j] = max(g[i] + cell[ i-1,j-p[i] ]，cell[i-1,j])
     * 时间复杂度 O(n*m)
     * 空间复杂度 O(m)
     */
    int getMaxGold3(int n, int m, int[] g, int[] p) {
        // 包含0个工人
        int[] preResults = new int[m + 1];
        int[] results = new int[m + 1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j < p[i]) {
                    results[j] = preResults[j];
                } else {
                    results[j] = Math.max(preResults[j], preResults[j - p[i]] + g[i]);
                }
                System.out.printf("%3s, ", results[j]);
            }
            System.out.println();
            preResults = Arrays.copyOf(results, m + 1);
        }
        return results[m];
    }

    public static void main(String[] args) {
        GoldMine goldMine = new GoldMine();
        // 内部顺序随意
        int[] gold = new int[]{400, 500, 200, 300, 350};
        int[] goldPerson = new int[]{5, 5, 3, 4, 3};
        System.out.println(goldMine.getMaxGold3(5, 10, gold, goldPerson));

        // 注意： 递归的时间复杂度和空间复杂度与n有关系，与m无关系；动态规划与两者 n和m都存在关系，故在实际应用中应根据实际情况选择最优的算法
        // 并不一定动态规划一定优秀。
    }
}
